#include <math.h>


/**
 * @brief 633. 平方数之和
 * https://leetcode.cn/problems/sum-of-square-numbers/
 */
class Solution {
public:
    bool judgeSquareSum(int c) {
        if (c == 0) return true;

        using ull = unsigned long long;
        ull l = 0;
        ull r = sqrt(c);  //* 防止超时的关键

        while ( l <= r) {
            ull res = l*l + r*r;
            if (res > (ull)c) r--;
            else if (res < (ull)c) l++;
            else return true;
        }

        return false;
    }
};
